package pl.poznan.put.cs.to.tsp.localsearch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import pl.poznan.put.cs.to.tsp.common.Vertexes;

public class EdgeSwapMoveHandler implements IMoveHandler {
	private List<Integer> a;
	private List<Integer> b;

	private boolean leftFirst;
	private boolean leftSecond;

	private int indexFirst;
	private int indexSecond;

	private boolean inAFirst;

	private Vertexes vertexes;

	private boolean improved;

	private List<Integer> tmp;

	private Random r;

	private TabuManager tabuManager;

	public EdgeSwapMoveHandler(List<Integer> resA, List<Integer> resB,
			Vertexes vertexes, TabuManager tabuManager) {
		super();
		// System.out.println("start");
		this.a = resA;
		this.b = resB;
		this.vertexes = vertexes;
		this.r = new Random();
		this.tabuManager = tabuManager;

		// System.out.println(">BEFORE<");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);

		this.improved = this.tryEdgeSwapping();
		// System.out.println("end");

		// System.out.println(">AFTER<");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);
	}

	private boolean tryEdgeSwapping() {
		this.inAFirst = this.r.nextBoolean();

		if (this.inAFirst) {
			if (this.a.size() == 0) {
				// System.out.println("exited");
				return false;
			}
			this.indexFirst = this.a.get(this.r.nextInt(this.a.size()));
		} else {
			if (this.b.size() == 0) {
				// System.out.println("exited");
				return false;
			}
			this.indexFirst = this.b.get(this.r.nextInt(this.b.size()));
		}

		this.leftFirst = this.r.nextBoolean();

		int actualFirst = this.indexFirst;
		int actualSecond;

		int tabuFirst = -1;
		int tabuSecond = -1;
		int tabuDelta = Integer.MAX_VALUE;

		do {
			this.indexSecond = this.drawSecond(actualFirst);
			// System.out.println("indexFirst: " + this.indexFirst
			// + ", indexSecond: " + this.indexSecond);
			if (this.indexSecond >= 0) {
				actualSecond = this.indexSecond;

				this.leftSecond = this.r.nextBoolean();
				// System.out.println("second drawn");
				do {
					int delta = this.simulateMove(actualFirst, actualSecond);
					if (delta < 0) {
						if (this.tabuManager.isTabuVertex(Integer
								.valueOf(actualFirst))
								|| this.tabuManager.isTabuVertex(Integer
										.valueOf(actualSecond))) {
							// System.out.println("tabu found");
							if ((tabuFirst == -1 && tabuSecond == -1)
									|| (delta < tabuDelta)) {
								tabuFirst = actualFirst;
								tabuSecond = actualSecond;
								tabuDelta = delta;
							}
						} else {
							// System.out.println("not tabu");
							this.performMove(actualFirst, actualSecond);

							this.tabuManager.add(actualFirst);
							this.tabuManager.add(actualSecond);

							return true;
						}
					}

					actualSecond = this.findNextSecondVertex(actualFirst,
							actualSecond);
					// System.out.println("new second found: " + actualSecond
					// + " | " + this.indexSecond + " |");
				} while (actualSecond != this.indexSecond);

				if (this.leftFirst) {
					actualFirst = (actualFirst - 1 + this.a.size() + this.b
							.size())
							% (this.a.size() + this.b.size());
				} else {
					actualFirst = (actualFirst + 1)
							% (this.a.size() + this.b.size());
				}
				// System.out.println("new first found");
				this.inAFirst = this.a.contains(actualFirst);
			} else {
				break;
			}

			// System.out.println("[" + actualFirst + ", " + actualSecond
			// + "] , [" + tabuFirst + ", " + tabuSecond + "]");
		} while (actualFirst != this.indexFirst);

		if (tabuFirst != -1 && tabuSecond != -1) {
			this.performMove(tabuFirst, tabuSecond);

			this.tabuManager.add(tabuFirst);
			this.tabuManager.add(tabuSecond);

			// System.out.println("TABU result used!");
			return true;
		}

		return false;
	}

	private void performMove(int pred1, int pred2) {
		this.inAFirst = this.a.contains(pred1);
		List<Integer> x;
		if (this.inAFirst) {
			x = this.a;
		} else {
			x = this.b;
		}

		int succ1 = x.get((x.indexOf(pred1) + 1) % x.size());
		int succ2 = x.get((x.indexOf(pred2) + 1) % x.size());

		ArrayList<Integer> newList = new ArrayList<Integer>();

		int index = (x.indexOf(succ2) + 1) % x.size();
		while (index != x.indexOf(pred1)) {
			newList.add(x.get(index));
			index = (index + 1) % x.size();
		}

		newList.add(pred1);
		newList.add(pred2);

		index = (x.indexOf(pred2) - 1 + x.size()) % x.size();
		while (index != x.indexOf(succ1)) {
			newList.add(x.get(index));
			index = (index - 1 + x.size()) % x.size();
		}

		newList.add(succ1);
		newList.add(succ2);

		if (this.inAFirst) {
			this.a = newList;
		} else {
			this.b = newList;
		}
	}

	private int simulateMove(int pred1, int pred2) {
		List<Integer> x;
		if (this.inAFirst) {
			x = this.a;
		} else {
			x = this.b;
		}

		int succ1 = x.get((x.indexOf(pred1) + 1) % x.size());
		int succ2 = x.get((x.indexOf(pred2) + 1) % x.size());

		int pred1succ1 = this.vertexes.getDistanceBetween(pred1, succ1);
		int pred2succ2 = this.vertexes.getDistanceBetween(pred2, succ2);
		int pred1pred2 = this.vertexes.getDistanceBetween(pred1, pred2);
		int succ1succ2 = this.vertexes.getDistanceBetween(succ1, succ2);

		int delta = (pred1pred2 + succ1succ2) - (pred1succ1 + pred2succ2);
		return delta;
	}

	// private void printList(List<Integer> list) {
	// for (int i : list) {
	// // System.out.print(i + " ");
	// }
	// // System.out.println();
	// // System.out.println("n = " + list.size());
	// }

	private int findNextSecondVertex(int f, int s) {
		if (this.a.contains(s)) {
			this.tmp = this.a;
		} else {
			this.tmp = this.b;
		}

		int iF = this.tmp.indexOf(f);
		int iFprev = (iF - 1 + this.tmp.size()) % this.tmp.size();
		int iFsucc = (iF + 1) % this.tmp.size();
		int iS = this.tmp.indexOf(s);

		if (this.leftSecond) {
			int x = (iS - 1 + this.tmp.size()) % this.tmp.size();

			if (x == iFsucc) {
				x = (iFprev - 1 + this.tmp.size()) % this.tmp.size();
				return this.tmp.get(x);
			} else {
				return this.tmp.get(x);
			}
		} else {
			int x = (iS + 1) % this.tmp.size();

			if (x == iFprev) {
				x = (iFsucc + 1) % this.tmp.size();
				return this.tmp.get(x);
			} else {
				return this.tmp.get(x);
			}
		}
	}

	private int drawSecond(int actualFirst) {
		if (this.inAFirst) {
			this.tmp = this.a;
		} else {
			this.tmp = this.b;
		}

		if (this.tmp.size() < 4) {
			return -1;
		}

		int indexOfFirst = this.tmp.indexOf(actualFirst);
		int iFprev = (indexOfFirst - 1 + this.tmp.size()) % this.tmp.size();
		int iFsucc = (indexOfFirst + 1) % this.tmp.size();

		int random = this.r.nextInt(this.tmp.size() - 3);

		if (random == (indexOfFirst)) {
			if (r.nextBoolean()) {
				return this.tmp.get((iFsucc + 1) % this.tmp.size());
			} else {
				return this.tmp.get((iFprev - 1 + this.tmp.size())
						% this.tmp.size());
			}
		}
		if (random == iFprev) {
			return this.tmp.get((iFprev - 1 + this.tmp.size())
					% this.tmp.size());
		}
		if (random == iFsucc) {
			return this.tmp.get((iFsucc + 1) % this.tmp.size());
		}

		return this.tmp.get(random);
	}

	@Override
	public boolean hasImproved() {
		return this.improved;
	}

	@Override
	public List<Integer> getA() {
		return a;
	}

	@Override
	public List<Integer> getB() {
		return b;
	}
}
